#include <iostream>
#include <vector>
#include <queue>

using namespace std;
// 429. N 叉树的层序遍历
// 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

void printRes(vector<vector<int>>& res) {
    cout << "[";
    for(int i = 0; i < res.size(); i++) {
        cout << "[";
        for(int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if(j < res[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if(i < res.size() - 1)
            cout << ",";
    }
    cout << "]" << endl;
}
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;

        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            int sz = q.size();
            vector<int> levelNodes;
            for(int i = 0; i < sz; i++) {
                Node* head = q.front();
                q.pop();
                levelNodes.push_back(head->val);
                for(Node* child : head->children) {
                    q.push(child);
                }
            }
            res.push_back(levelNodes);
        }
        return res;
    }
};
int main() {
    Node* tree1 = new Node(1, vector<Node*>({
        new Node(3,vector<Node*>({new Node(5), new Node(6)})),
        new Node(2),
        new Node(4)
    }));
    vector<vector<int>> res1 = Solution().levelOrder(tree1);
    printRes(res1);

    Node* tree2 = new Node(1,vector<Node*>({
        new Node(2),
        new Node(3,vector<Node*>({new Node(6), new Node(7,vector<Node*>({new Node(11,vector<Node*>({new Node(14)}))}))})),
        new Node(4,vector<Node*>({new Node(8,vector<Node*>({new Node(12)}))})),
        new Node(5,vector<Node*>({new Node(9,vector<Node*>({new Node(13)})),new Node(10)}))
    }));
    vector<vector<int>> res2 = Solution().levelOrder(tree2);
    printRes(res2);
    return 0;
}
